/**
* @author AlbertDarren
* @contact 2563491540@qq.com
*/
#include <cstdio>
#include <unordered_map>
#include <ctime>
using namespace std;
// F(n)=F(n-1)+F(n-2),F(0)=F(1)=1
long long F1(long long n)// 28.592848 s
{
    if (n==0||n==1)
    {
        return 1;
    }
    return F1(n-1)+F1(n-2);
}
long long F2(long long n,unordered_map<long long,long long> &table)//0.000043 s
{
    if (table[n]!=0)
    {
        return table[n];
    }
    else
    {
        long long f;
        if (n<=1)
        {
            f=1;
        }
        else
        {
            f=F2(n-1,table)+F2(n-2,table);
        }
        table[n]=f;
        return f;
    }

}
long long F3(long long n)//0.000027
{
    unordered_map<long long,long long> mp;
    for (long long i=0;i<=n ;++i )
    {
        long long f;
        if (i<=1)
        {
            f=1;
        }
        else
        {
            f=mp[i-1]+mp[i-2];
        }
        mp[i]=f;
    }
    return mp[n];
}
int main_96()
{
    clockid_t start=clock();
    long long num=48;
    long long res=F1(num);
    if (res<0)
    {
        printf("integer overflow!\n");
    }
    else
    {
        printf("%lld\n",res);
    }
    clockid_t end_t=clock();
    printf("It takes %lf s\n",(double)(end_t-start)/CLOCKS_PER_SEC);
    unordered_map<long long,long long> hash_table;
    res=F2(num,hash_table);
    if (res<0)
    {
        printf("integer overflow!\n");
    }
    else
    {
        printf("%lld\n",res);
    }
    start=end_t;
    end_t=clock();
    printf("It takes %lf s\n",(double)(end_t-start)/CLOCKS_PER_SEC);
    res=F3(num);
    if (res<0)
    {
        printf("integer overflow!\n");
    }
    else
    {
        printf("%lld\n",res);
    }
    printf("It takes %lf s\n",(double)(clock()-end_t)/CLOCKS_PER_SEC);
	return 0;
}
